1605D - Treelabeling - CodeForces Solution

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <iomanip>
#include <queue>
#include <deque>
#define M_PIl 3.141592653589793238462643383279502884L
#define endl '\n'
#define N 400010
#define K first
#define V second

using namespace std;
typedef long long ll;
typedef long double ld;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll,ll> pll;
const ld prec = 1e-9;
const ll NN = 2*1e5;
const ll MOD = 1000000007;

void dfs(int parent, vvi &adj, set<int> &blue, set<int> &red, bool parentBlue){

    for(int child : adj[parent]){
        if(blue.count(child) || red.count(child)){
            continue;
        }

        (parentBlue ? red : blue).insert(child);
        dfs(child, adj, blue, red, !parentBlue);
    }

}

//returns true if the most significant on bit in a is also on in b
bool shareBit(int a, int b){
    int c = 1;
    while(a){
        a /= 2;
        c *= 2;
    }
    c /= 2;
    return b & c;
}

void run()
{

    int n; cin >> n;
    vvi adj(n, vi(0));
    for(int i = 0; i < n-1; i++){
        int u,v; cin >> u >> v;
        u--; v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    set<int> small;
    set<int> large;

    dfs(0, adj, small, large, true);

    if(((int) small.size()) > ((int) large.size())){
        swap(small, large);
    }

    vi ans(n, 0);
    int s = (int) small.size();
    for(int i = 1; i <= n; i++){
        if(shareBit(i,s)){
            ans[*small.begin()] = i;
            small.erase(*small.begin());
        }
        else{
            ans[*large.begin()] = i;
            large.erase(*large.begin());
        }  
    }

    for(int i = 0; i < n; i++) cout << ans[i] << " \n"[i==n-1];   

}
int main()
{
    //jim
    //KING OF THE WORLD...... U.W.T.B
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout << fixed << setprecision(20);
    //USE LONG LONGS

    int t; cin>>t; while(t--) run();
}